Search results for "Team Orienteering Problem"

showing 2 items of 2 documents

A branch-and-cut algorithm for the Team Orienteering Problem

2017

The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two-index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch-and-cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.

branch-and-cut algorithm; Team Orienteering Problem; two-index mathematical formulation; Computer Science Applications1707 Management Science and Operations Research;0209 industrial biotechnologyMathematical optimization021103 operations researchStrategy and Management0211 other engineering and technologiesOrienteering02 engineering and technologyManagement Science and Operations ResearchComputer Science Applicationstwo-index mathematical formulationTravel timeComputer Science Applications1707 Management Science and Operations Research020901 industrial engineering & automationManagement of Technology and InnovationBenchmark (computing)Limit (mathematics)branch-and-cut algorithmTeam Orienteering ProblemBusiness and International ManagementBranch and cutAlgorithmPolynomial numberMathematics
researchProduct

A matheuristic for the Team Orienteering Arc Routing Problem

2015

In the Team OrienteeringArc Routing Problem (TOARP) the potential customers are located on the arcs of a directed graph and are to be chosen on the basis of an associated profit. A limited fleet of vehicles is available to serve the chosen customers. Each vehicle has to satisfy a maximum route duration constraint. The goal is to maximize the profit of the served customers. We propose a matheuristic for the TOARP and test it on a set of benchmark instances for which the optimal solution or an upper bound is known. The matheuristic finds the optimal solutions on all, except one, instances of one of the four classes of tested instances (with up to 27 vertices and 296 arcs). The average error o…

MatheuristicMathematical optimizationInformation Systems and ManagementGeneral Computer ScienceComputer scienceOrienteeringDirected graphManagement Science and Operations ResearchUpper and lower boundsIndustrial and Manufacturing EngineeringVertex (geometry)Constraint (information theory)Set (abstract data type)Routing problems with profitsArc routing problemModeling and SimulationBenchmark (computing)Team Orienteering ProblemDuration (project management)MATEMATICA APLICADAArc routing
researchProduct